--[[ Copyright 2012, Chris Ho                               ]]--
--[[ MIT License (Please read the LICENSE file for details) ]]--

Use("common/Quicksort");

-- List Utility (from RO's Utility Library)
-- By default, we sort using in-place Quicksort. You may define a
-- SORTER global to specify an alternate sorting module.
List = {}

function List.new ()
	return { first = 0, last = -1}
end

function List.pushleft (list, value)
	local first = list.first-1
	list.first  = first
	list[first] = value;
end

function List.pushright (list, value)
	local last = list.last + 1
	list.last = last
	list[last] = value
end

function List.popleft (list)
	local first = list.first
	if first > list.last then 
		return nil
	end
	local value = list[first]
	list[first] = nil         -- to allow garbage collection
	list.first = first+1
	return value
end

function List.popright (list)
	local last = list.last
	if list.first > last then
		return nil
	end
	local value = list[last]
	list[last] = nil
	list.last = last-1
	return value 
end

function List.clear (list)
	for i,v in ipairs(list) do
		list[i] = nil
	end
--[[
	if List.size(list) == 0 then
		return
	end
	local first = list.first
	local last  = list.last
	for i=first, last do
		list[i] = nil
	end
--]]
	list.first = 0
	list.last = -1
end

function List.size (list)
	local size = list.last - list.first + 1
	return size
end

function List.sort(list, _sorter)
  if (SORTER == nil) then
    Quicksort.Sort(list, list.first, list.last, _sorter);
  else
    SORTER.Sort(list, list.first, list.last, _sorter);
  end
end
